#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
#include<List>

typedef struct Listnode
{
	struct Listnode* next;
	int val;
}ListNode;

ListNode* sortList(ListNode* head)
{
	if (head == nullptr || head->next == nullptr)
	{
		return head;
	}

	ListNode* fast = head->next, * slow = head;

	while (fast && fast->next)
	{
		slow = slow->next;
		fast = fast->next->next;
	}

	ListNode* temp = slow->next;
	slow->next = nullptr;
	ListNode* left = sortList(head);
	ListNode* right = sortList(temp);
	ListNode res;
	ListNode* h = &res;
	res.next = NULL;

	while (left && right)
	{
		if (left->val <= right->val)
		{
			h->next = left;
			left = left->next;
		}
		else
		{
			h->next = right;
			right = right->next;
		}
		h = h->next;
	}
	h->next = left ? left : right;
	return res.next;
}

//ListNode* merge(ListNode* left, ListNode* right) {
//	ListNode dummy;
//	ListNode* tail = &dummy;
//	dummy.next = NULL;
//
//	while (left && right) {
//		if (left->val <= right->val) {
//			tail->next = left;
//			left = left->next;
//		}
//		else {
//			tail->next = right;
//			right = right->next;
//		}
//		tail = tail->next;
//	}
//
//	tail->next = left ? left : right;
//
//	return dummy.next;
//}
//
//ListNode* sortList(ListNode* head) {
//	if (head == NULL || head->next == NULL) {
//		return head;
//	}
//
//	ListNode* slow = head;
//	ListNode* fast = head->next;
//
//	while (fast && fast->next) {
//		slow = slow->next;
//		fast = fast->next->next;
//	}
//
//	ListNode* right = sortList(slow->next);
//	slow->next = NULL;
//	ListNode* left = sortList(head);
//
//	return merge(left, right);
//}

int main()
{
	ListNode a;
	a.val = 5;
	ListNode b;
	b.val = 3;
	a.next = &b;
	ListNode c;
	c.val = 4;
	b.next = &c;
	c.next = NULL;

	ListNode* head = sortList(&a);
	printf("%d", head->val);
	printf("%d", head->next->val);
	printf("%d", head->next->next->val);
	return 0;
}